package com.foxzzz.dynamic.programming;

import com.foxzzz.base.GenUtil;

public class Solution211 {

    public static void main(String[] args) {
        System.out.println(new Solution211().maximalSquare(GenUtil.genCharTestCast("[[\"1\",\"0\",\"1\",\"0\"],[\"1\",\"0\",\"1\",\"1\"],[\"1\",\"0\",\"1\",\"1\"],[\"1\",\"1\",\"1\",\"1\"]]"
                , 4, 4)));
        System.out.println(new Solution211().maximalSquare(GenUtil.genCharTestCast("[[\"0\",\"0\",\"0\",\"1\"],[\"1\",\"1\",\"0\",\"1\"],[\"1\",\"1\",\"1\",\"1\"],[\"0\",\"1\",\"1\",\"1\"],[\"0\",\"1\",\"1\",\"1\"]]",
                4, 5)));
        System.out.print(new Solution211().maximalSquare(GenUtil.genCharTestCast("[[\"1\",\"0\",\"1\",\"0\",\"0\"],[\"1\",\"0\",\"1\",\"1\",\"1\"],[\"1\",\"1\",\"1\",\"1\",\"1\"],[\"1\",\"0\",\"0\",\"1\",\"0\"]]",
                5, 4)));
    }

    public int maximalSquare(char[][] matrix) {
        if (matrix.length == 0)
            return 0;
        int[][] dp = new int[matrix.length][matrix[0].length];
        int max = 0;
        for (int i = 0; i < matrix[0].length; i++) {
            dp[0][i] = matrix[0][i] == '1' ? 1 : 0;
            max = Math.max(max, dp[0][i]);
        }
        for (int i = 0; i < matrix.length; i++) {
            dp[i][0] = matrix[i][0] == '1' ? 1 : 0;
            max = Math.max(max, dp[i][0]);
        }

        for (int i = 1; i < matrix.length; i++) {
            for (int j = 1; j < matrix[0].length; j++) {
                if (dp[i - 1][j - 1] > 0 && matrix[i][j] == '1') {

                    int num = dp[i - 1][j - 1];
                    int len = num;
                    while (num > 0) {

                        if (matrix[i - num][j] == '0' || matrix[i][j - num] == '0') {
                            len = num - 1;
                        }
                        num--;
                    }
                    dp[i][j] = len + 1;

                } else {
                    dp[i][j] = matrix[i][j] == '1' ? 1 : 0;
                }
                max = Math.max(dp[i][j], max);
            }
        }
        return max * max;

    }
}
